package 树;

import org.w3c.dom.ls.LSInput;
import 动态链表.LinkedList;

import java.util.Iterator;

/**
 * 二分搜索树
 */
public class BinarySearchTree<E extends Comparable<E>> implements Iterable<E> {
    private class Node{
        public E e;
        public Node left,right;
        public Node(E e){
            this.e = e;
            this.left = null;
            this.right = null;
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node root;
    private int size;

    public BinarySearchTree(){
        root = null;
        size = 0;
    }

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0 && root == null;
    }

    public void clear(){
        root = null;
        size = 0;
    }

    public void add(E e){
        root = add(root,e);
    }

    //添加节点，和当前根节点比较，如果比根节点大的话就在根节点的右边添加，否则就在根节点的左边添加
    private Node add(Node node,E e){
        if (node == null){
            //为空就是到了树的叶子节点，size++创建一个新的节点返回
            size++;
            return new Node(e);
        }
        if (e.compareTo(node.e) < 0){
            //比根节点小的换就在左边添加，一直比较之后返回到上一层做一个新的连接
            node.left = add(node.left,e);
        }else if(e.compareTo(node.e) > 0) {
            node.right = add(node.right,e);
        }
        //最后返回该节点
        return node;
    }

    public boolean contains(E e){
        return contains(root,e);
    }

    private boolean contains(Node node, E e){
        //如果最后的节点为空的换就是没有找到该元素，就是没有包含该元素直接返回false
        if (node == null){
            return false;
        }
        //每次递归和根节点比较小于的话就去左边比较，大于的话就去右边比较，相等的话就返回true，并且每一层都要向上一层返回信息
        if (e.compareTo(node.e) < 0){
            return contains(node.left, e);
        }else if (e.compareTo(node.e) > 0){
            return contains(node.right,e);
        }else {
            return true;
        }
    }

    //深度优先遍历
    //前序遍历-递归
    public void perOrder(){
        perOrder(root);
    }

    private void perOrder(Node node){
        if (node == null){
            return;
        }
        System.out.print(node.e + " ");
        perOrder(node.left);
        perOrder(node.right);
    }

    //前序遍历-迭代
    public void preOrderNR(){
        LinkedList<Node> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()){
            Node cur = stack.pop();
            System.out.print(cur.e + " ");
            if (cur.right != null){
                stack.push(cur.right);
            }
            if (cur.left != null){
                stack.push(cur.left);
            }
        }

    }

    //中序遍历-递归
    public void inOrder(){
        inOrder(root);
    }

    private void inOrder(Node node){
        if (node == null){
            return;
        }
        inOrder(node.left);
        System.out.print(node.e + " ");
        inOrder(node.right);
    }

    //中续遍历-迭代
    public void inOrderNR(){
        LinkedList<Node> stack = new LinkedList<>();
        Node p = root;
        while (p != null){
            stack.push(p);
            p = p.left;
        }
        while (!stack.isEmpty()){
            Node cur = stack.pop();
            System.out.print(cur.e + " ");
            if (cur.right != null){
                p = cur.right;
                while (p != null){
                    stack.push(p);
                    p = p.left;
                }
            }

        }

    }


    //后续遍历-递归
    public void postOrder(){
        postOrder(root);
    }

    private void postOrder(Node node){
        if (node == null){
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.e + " ");
    }

    //后续遍历-迭代
    public void postOrderNR(){
        LinkedList<Node> stack = new LinkedList<>();
        Node p = root;
        Node flag = null;
        while (p != null){
            stack.push(p);
            p = p.left;
        }

        while (!stack.isEmpty()){
            Node cur = stack.pop();
            //如果当前节点的右儿子与flag相同，说明当前节点右子树已完成遍历
            if (cur.right == null || cur.right == flag){
                System.out.print(cur.e + " ");
                flag = cur;
            }else {
                stack.push(cur);
                cur = cur.right;
                while (cur != null){
                    stack.push(cur);
                    cur = cur.left;
                }
            }
        }
    }


    //广度优先遍历-层序遍历
    public void levelOrder(){
        LinkedList<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            Node cur = queue.poll();
            System.out.print(cur.e + " ");
            if (cur.left != null){
                queue.offer(cur.left);
            }
            if (cur.right != null){
                queue.offer(cur.right);
            }
        }
    }

    //获取最大和最小值
    public E minimum(){
        if (size == 0){
            throw new IllegalArgumentException("BST is empty");
        }
        return minimum(root).e;
    }

    private Node minimum(Node node){
        if (node.left == null){
            return node;
        }
        return minimum(node.left);
    }

    public E maximum(){
        if (size == 0){
            throw new IllegalArgumentException("BST is empty");
        }
        return maximum(root).e;
    }

    private Node maximum(Node node){
        if (node.right == null){
            return node;
        }
        return maximum(node.right);
    }

    //删除最大最小值
    public E removeMin(){
        E ret = minimum();
        root = removeMin(root);
        return ret;
    }

    public Node removeMin(Node node){
        if (node.left == null){
            //获取最小值的右子树，并断开最小元素与右子树的连接，返回右子树，对上一层重新连接
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }
        node.left = removeMin(node.left);
        return node;
    }

    public E removeMax(){
        E ret = maximum();
        root = removeMax(root);
        return ret;
    }

    public Node removeMax(Node node){
        if (node.right == null){
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }
        node.right = removeMax(node.right);
        return  node;
    }

    //删除二叉搜索树中的指定的值
    public void remove(E e){
        root = remove(root, e);
    }

    private Node remove(Node node, E e){
        if (node == null){
            return  null;
        }
        if (e.compareTo(node.e) < 0){
            node.left = remove(node.left,e);
            return node;
        }else if(e.compareTo(node.e) > 0){
            node.right = remove(node.right,e);
            return node;
        }else{
            //左子树为空
            if (node.left == null){
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
            //右子树为空
            if (node.right == null){
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }
            //左右都不为空
            //为了保证二分搜索树中序遍历的连贯性
            //最好将离待删除结点最近的结点上位
            //上位的点为：待删除结点左子树的最大值 或者是 待删除结点右子树的最小值

            //先找到左子树的最大值
            Node ret = maximum(node.left);
            //删除左子树的最大值 并将左子树的新根 给最大值的左腿接上
            ret.left = removeMax(ret);
            //把待删除结点的右腿给最大值右腿接上
            ret.right = node.right;
            //待删除结点自废双腿
            node.left = node.right = null;
            return ret;

        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        generateBST(root,0,sb);
        return sb.toString();

    }

    private void generateBST(Node node, int depth, StringBuilder sb) {
        if (node == null){
            sb.append(generateDepth(depth) + "null\n");
            return;
        }
        sb.append(generateDepth(depth) + node.e + "\n");
        generateBST(node.left,depth + 1,sb);
        generateBST(node.right,depth + 1,sb);
    }

    private String generateDepth(int depth) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            sb.append("--");
        }
        return sb.toString();
    }


    @Override
    public boolean equals(Object obj) {
        if (obj == null){
            return false;
        }
        if (this == obj){
            return true;
        }
        if (obj instanceof BinarySearchTree){
            BinarySearchTree other = (BinarySearchTree) obj;
            if (this.size == other.size){
                //如果长度相等的话就比较，其结构和数据的一致性
//                return isSameWithStructureAndData(root,other.root);
                //比较数据是否相等，不管结构
                return this.inOrderList().equals(other.inOrderList());
            }else {
                return false;
            }
        }else {
            return false;
        }
    }

    private LinkedList<E> inOrderList() {
        LinkedList<E> list = new LinkedList<>();
        LinkedList<Node> stack = new LinkedList<>();
        Node p = root;
        while (p != null){
            stack.push(p);
            p = p.left;
        }
        while (!stack.isEmpty()){
            Node cur = stack.pop();
            list.add(cur.e);
            if (cur.right != null){
                p = cur.right;
                while (p != null){
                    stack.push(p);
                    p = p.left;
                }
            }
        }
        return list;
    }

    private boolean isSameWithStructureAndData(Node node1, Node node2) {
        //如果左右节点都为空的话就说名这两个二叉搜索树是结构和数据是相等的
        if (node1 == null && node2 == null){
            return true;
        }
        //只要这两个中有一个值不相等的话就返回false，值不相等
        if (!node1.e.equals(node2.e)){
            return false;
        }
        //递归判断该子树的左边是否结构和数据相等，同理判断右边，最后返回判断后的左右子树的比较的结果
        boolean flag1 = isSameWithStructureAndData(node1.left, node2.left);
        boolean flag2 = isSameWithStructureAndData(node1.right, node2.right);
        return flag1 && flag2;
    }


    @Override
    public Iterator<E> iterator() {
        return new BSTIterator();
    }

    public class BSTIterator implements Iterator<E>{
        //将二叉树的中序遍历，拆分为循环的初始化，结束条件，循环体，步长来迭代该二叉搜索树
        LinkedList<Node> stack = new LinkedList<>();
        Node p = root;

        public BSTIterator(){
            while (p != null){
                stack.push(p);
                p = p.left;
            }
        }

        @Override
        public boolean hasNext() {
            return !stack.isEmpty();
        }

        @Override
        public E next() {
            Node cur = stack.pop();
            E ret = cur.e;
            if (cur.right != null){
                p = cur.right;
                while (p != null){
                    stack.push(p);
                    p = p.left;
                }
            }
            return ret;
        }
    }


//    public class BSTIterator implements Iterator<E>{
//        //通过内部中序遍历获得一个集合后，在通过集合来迭代输出结果
//        LinkedList<E> list = inOrderList();
//
//        @Override
//        public boolean hasNext() {
//            return !list.isEmpty();
//        }
//
//        @Override
//        public E next() {
//            return list.removeFirst();
//        }
//    }
}
